//https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=13&tqId=23260&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
// 感觉牛客网代有bug ，输出的这个模值没看懂为什么！！！；

#include <iostream>
#include <vector>
using namespace std;

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int count = 0;
    int InversePairs(vector<int>& nums) {
        // write code here
        if (nums.size() < 2) return 0;
        mergeSort(nums,0,nums.size()-1);
        return count;
    }

    void mergeSort(vector<int>& nums, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = l + ((r - l) >> 1);
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        merge(nums, l, mid, r);
    }

    void merge(vector<int>& nums, int l, int m, int r) {
        std::vector<int> help(r-l+1);
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        while (p1 <= m && p2 <= r) {
            if (nums[p1] > nums[p2]) { // 重点代码
                count = count + (m-p1)+1;
                count %=1000000007; 
            }
            help[i++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++];
        }
        while (p1 <= m ) {
            help[i++] = nums[p1++];
        }
        while (p2 <= r ) {
            help[i++] = nums[p2++];
        }
        for (i = 0; i < r - l + 1 ; ++i) {
            nums[l + i] = help[i];
        }
    }
};